class Solution {//leetcode62——不同路径
private:
    int dfs(int i,int j){
        if(i==0||j==0) return 0;//不合法的位置
        if(i==1&&j==1) return 1;
        if(memory[i][j]!=0) return memory[i][j];

        memory[i][j]= dfs(i-1,j)+dfs(i,j-1);
        return memory[i][j];
    }
public:
    int uniquePaths(int m, int n) {
        memory.resize(m+1,vector<int>(n+1));
        return dfs(m,n);
    }
private:vector<vector<int>> memory;
};